package main

import "fmt"

// 如何找出数组中出现 1 次的数

func main() {
	arr := []int{6, 3, 4, 5, 9, 4, 3}
	fmt.Println(findSingle(arr))
}

func findSingle(arr []int) int {
	length := len(arr)
	for i := 0; i < 32; i++ {
		count0, count1 := 0, 0
		result0, result1 := 0, 0

		for j := 0; j < length; j++ {
			if isOne(arr[j], i) {
				result1 ^= arr[j]
				count1++
			} else {
				result0 ^= arr[j]
				count0++
			}
		}

		if count1%2 == 1 && result0 != 0 {
			return result1
		}

		if count0%2 == 1 && result1 != 0 {
			return result0
		}
	}

	return -1
}

func isOne(data, index int) bool {
	data = data >> index
	return data%2 == 1
}
